package 题目集.滑动窗口.ch02_不定长窗口;

import org.junit.Test;

import java.util.Arrays;

/**
 * 有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
 * 假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
 * 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
 * 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
 * 请返回待替换子串的最小可能长度。
 * 如果原字符串自身就是一个平衡字符串，则返回 0。
 * https://leetcode.cn/problems/replace-the-substring-for-balanced-string/description/
 */
public class ch05_替换子串得到平衡字符串 {
    /**
     * 暴力解：
     *      统计每个字符的个数，其中超过平均数的字符个数就是需要替换的字母个数。
     *      枚举每一个起点，查看以该起点为起点的子串中是否包含所有需要替换的字符。
     * 滑动窗口优化：
     *      1.统计出每个要替换字符的个数。统计出要替换总数sum。
     *      2.用一个变量cnt表示窗口可以被替换的数量。
     *      3.当cnt==sum时表示一个符合条件的解，窗口左缩。如果移除的字符是要替换的字符，则cnt--。
     *      4.当cnt<sum时表示不符合条件，窗口右扩。如果右扩的字符是要替换的字符，则cnt++。
     */
    public int balancedString(String s) {
        int n = s.length();
        int avg = n / 4;
        int[] count = new int[26];
        Arrays.fill(count, -avg);
        for (int i = 0; i < n; i++) {
            count[s.charAt(i) - 'A']++;
        }
        int sum = 0;
        for (int c : count) {
            if (c > 0) {
                sum += c;
            }
        }
        if (sum == 0) return 0; //原字符串就是平衡字符串
        int cnt = 0;
        int res = n;
        for (int i = 0, j = 0; j < n; j++) {
            if (count[s.charAt(j) - 'A']-- > 0) {   //右扩的字符是要替换的字符
                cnt++;
            }
            if (cnt >= sum) {
                while (cnt>=sum){
                    if (count[s.charAt(i) - 'A'] >= 0) {   //左缩的字符是要替换的字符
                        cnt--;
                    }
                    count[s.charAt(i) - 'A']++;
                    i++;
                }
                res = Math.min(res, j - i + 2); //这里j-i+2,第一个1是因为i从0开始，第二个1上面的while结束条件是cnt<sum，所以i多移动了一次
            }
        }
        return res;
    }

    @Test
    public void test() {
        //w=8,e=4,q=5,r=3
        String s = "QQQW";
        System.out.println(balancedString(s));
    }
}
